#include "binary_patterns.h"
#include "grate/util/compact_queue.h"

namespace growth_rate {
namespace binary_patterns {

static const size_t kMaxWordLength = 10000;

bool Pattern_4X_4Y::handle_xy_root(const Word &root, size_t xlen) {
  size_t xylen = root.length();
  size_t ylen = xylen - xlen;
  CHECK_GT(xlen, 0);
  CHECK_LT(xlen, xylen);
  uint8_t buffer[kMaxWordLength];
  size_t total_len = 4 * xylen;
  CHECK_LT(total_len, kMaxWordLength);
  Word word = build_xy_pattern(buffer, options_.pattern,
                               root.prefix(xlen), root.suffix(ylen));
  DCHECK_EQ(total_len, word.length());
  if (has_factor_forbidden_by_trie(word))
    return false;
  CHECK(add_lexmin_word(word));
  return true;
}

bool Pattern_4X_4Y::handle_cubic_root(const Word &root) {
  uint8_t buffer[kMaxWordLength];
  size_t total_len = 3 * root.length();
  CHECK_LT(total_len, kMaxWordLength);
  Word word = build_xy_pattern(buffer, "xxx", root, /* unused */ root);
  DCHECK_EQ(total_len, word.length());
  if (has_factor_forbidden_by_trie(word))
    return false;
  CHECK(add_lexmin_word(word));
  return true;
}

bool Pattern_4X_4Y::construct() {
  uint8_t buffer[kMaxWordLength];

  size_t pattern_queue_capacity = options_.queue_capacity - 1;
  size_t xxx_queue_capacity = 1;
  if (avoid_xxx_) {
    pattern_queue_capacity = options_.queue_capacity / 2;
    xxx_queue_capacity = options_.queue_capacity / 2;
  }
  IncreasingLengthWordQueue pattern_queue(pattern_queue_capacity, 1);
  IncreasingLengthWordQueue xxx_queue(xxx_queue_capacity, 1);

  pattern_queue.push_word("aa");
  pattern_queue.push_word("ab");
  if (avoid_xxx_) {
    CHECK(add_lexmin_word("aaa"));
    xxx_queue.push_word("aa");
    xxx_queue.push_word("ab");
  }

  while (!pattern_queue.is_empty() || !xxx_queue.is_empty()) {
    size_t exp_pattern_length = (pattern_queue.is_empty()) ? -1UL
                                : pattern_queue.head_word_length() * 4;
    size_t exp_xxx_length = (xxx_queue.is_empty()) ? -1UL
                            : xxx_queue.head_word_length() * 3;

    if (exp_pattern_length <= exp_xxx_length) {
      Word root = pattern_queue.pop_word(buffer, kMaxWordLength);
      size_t xylen = root.length();
      for (size_t xlen = 1; xlen < xylen; xlen++)
        handle_xy_root(root, xlen);
      for (char letter = 'a'; letter <= 'b'; letter++) {
        if (can_extend_root(&root, letter))
          pattern_queue.push_word(root.append(letter));
      }
    } else {
      Word root = xxx_queue.pop_word(buffer, kMaxWordLength);
      handle_cubic_root(root);
      size_t len_for_next_root = 3 * (root.length() + 1);
      if (len_for_next_root <= 4 * options_.max_root_length) {
        for (char letter = 'a'; letter <= 'b'; letter++) {
          if (can_extend_root(&root, letter, false))
            xxx_queue.push_word(root.append(letter));
        }
      }
    }

    size_t queues_size = pattern_queue.get_size_in_bytes() +
                         xxx_queue.get_size_in_bytes();
    max_queue_size_ = Max(max_queue_size_, queues_size);
  }

  return true;
}

}  // namespace binary_patterns
}  // namespace growth_rate
